package class39;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class CherryPickup {

    public static int comeGoMaxPathSum(int[][] matrix) {
        return process(matrix, 0, 0, 0);
    }

    //matrix中没有负数
    //A和B，一定迈出相同的步数，同步走
    //两个人会共同到达右下角，返回两个人路径的最大累加和
    public static int process(int[][] matrix, int Ar, int Ac, int Br) {
        int N = matrix.length;
        int M = matrix[0].length;
        if (Ar == N - 1 && Ac == M - 1) {
            return matrix[Ar][Ac];
        }

        //没有到达右下角
        // A 下    B 右
        // A 下    B 下
        // A 右    B 右
        // A 右    B 下
        int Bc = Ar + Ac - Br;
        int ADownBRight = 0;
        if (Ar + 1 < N && Bc + 1 < M) {
            ADownBRight = process(matrix, Ar + 1, Ac, Br);
        }
        int ADownBDown = 0;
        if (Ar + 1 < N && Br + 1 < N) {
            ADownBDown = process(matrix, Ar + 1, Ac, Br + 1);
        }
        int ARightBRight = 0;
        if (Ac + 1 < M && Bc + 1 < M) {
            ARightBRight = process(matrix, Ar, Ac + 1, Br);
        }
        int ARightBDown = 0;
        if (Ac + 1 < M && Br + 1 < N) {
            ARightBDown = process(matrix, Ar, Ac + 1, Br + 1);
        }
        int nextBest = Math.max(Math.max(ADownBRight, ADownBDown), Math.max(ARightBRight, ARightBDown));

        int curNum = Ar == Br ? matrix[Ar][Ac] : matrix[Ar][Ac] + matrix[Br][Bc];
        int res = curNum + nextBest;
        return res;
    }


    public static int dp(int[][] matrix) {
        int M = matrix.length;
        int N = matrix[0].length;

        int[][][] dp = new int[M][N][M];

        //最后一个位置
        dp[M - 1][N - 1][M - 1] = matrix[M - 1][N - 1];
        //普通位置
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    dp[i][j][k] = Integer.MIN_VALUE;
                }
            }
        }
        return process2(matrix, 0, 0, 0, dp);
    }

    public static int process2(int[][] matrix, int Ar, int Ac, int Br, int[][][] dp) {
        if (dp[Ar][Ac][Br] != Integer.MIN_VALUE) {
            return dp[Ar][Ac][Br];
        }
        int N = matrix.length;
        int M = matrix[0].length;
        if (Ar == N - 1 && Ac == M - 1) {
            //A B来到右下角
            return matrix[N - 1][M - 1];
        }
        //没有到达右下角
        // A 下    B 右
        // A 下    B 下
        // A 右    B 右
        // A 右    B 下
        int Bc = Ar + Ac - Br;
        int ADownBRight = 0;
        if (Ar + 1 < N && Bc + 1 < M) {
            ADownBRight = process2(matrix, Ar + 1, Ac, Br, dp);
        }
        int ADownBDown = 0;
        if (Ar + 1 < N && Br + 1 < N) {
            ADownBDown = process2(matrix, Ar + 1, Ac, Br + 1, dp);
        }
        int ARightBRight = 0;
        if (Ac + 1 < M && Bc + 1 < M) {
            ARightBRight = process2(matrix, Ar, Ac + 1, Br, dp);
        }
        int ARightBDown = 0;
        if (Ac + 1 < M && Br + 1 < N) {
            ARightBDown = process2(matrix, Ar, Ac + 1, Br + 1, dp);
        }
        int nextBest = Math.max(Math.max(ADownBRight, ADownBDown), Math.max(ARightBRight, ARightBDown));

        int curNum = Ar == Br ? matrix[Ar][Ac] : matrix[Ar][Ac] + matrix[Br][Bc];
        int res = curNum + nextBest;
        dp[Ar][Ac][Br] = res;
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 1, 1, 1}
        };

        System.out.println(comeGoMaxPathSum(matrix));
        System.out.println(dp(matrix));
    }
}
